package leetcode; /**
 * description:
 * author:张腾
 * date:2021-06-17
 */

import java.util.*;

/**
 * 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
 */
//先中序遍历排序，再找到两个顺序不对的节点，再进行遍历交换他们的值
public class leetcode99 {

    List<Integer> list;
    public void recoverTree(TreeNode root) {
        int one = -1;
        int two = -1;
        list = new ArrayList<>();
        inOrder(root,list);
        for (int i = 0; i < list.size()-1; i++) {
            if (list.get(i+1)<list.get(i)){
                two = list.get(i+1);
                if (one==-1) one = list.get(i);
                else break;
            }
        }
        recover(root,2,one,two);
    }

    public void inOrder(TreeNode root, List<Integer> list){
        if (root==null) return;
        if (root.left!=null) inOrder(root.left,list);
        list.add(root.val);
        if (root.right!=null) inOrder(root.right,list);
    }

    public void recover(TreeNode root,int count,int one,int two){
        if (root!=null){
            if (root.val==one || root.val==two){
                root.val= root.val==one? two:one;
                count--;
                if (count==0) return;
            }

            recover(root.left,count,one,two);
            recover(root.right,count,one,two);
        }
    }
}
